As data processors are used more and more in real-time control systems, new techniques are required to ensure the efficient use of system resources. For example, in many multi-tasking systems, there are several tasks trying to share some of the same system resources, such as memory storage, a printer, or a port to a display screen. It is crucial in such multi-tasking systems that the shared system resources are used in the most efficient way possible. For example, if multiple tasks are sharing a resource, there must be a way to indicate which task is currently using the resource and whether that task is performing a function that must not be disturbed. Semaphores are used for this function in many multitasking systems.
Semaphores are a type of flag or status indicator that reflects the present status of a system resource. Usually the status information in a semaphore indicates whether or not the system resource is presently being used. In some multi-tasking systems, the semaphore may also include information about which task is using the resource, and possibly even the type of function being performed on the resource.
For example, a particular location in memory can be designated as the location of the semaphore for a shared variable X. If any task wants to use the shared variable X, that task must read the semaphore for the shared variable X by reading that particular location in memory. The variable X semaphore contains information on the status of the variable X, such as whether the variable X is currently reserved for exclusive access by a particular task. If the variable X semaphore indicates that the variable X is currently reserved and is thus busy, the new task must wait. The new task can continue to poll the variable X semaphore by periodically reading the variable X semaphore to see if the variable X is still being used or if it has become available.
Once the variable X semaphore indicates that the variable X is no longer reserved and thus available, the waiting task writes to the variable X semaphore to change its status to busy or nonavailable. The waiting task has thus effectively locked the variable X resource for its own use. No other tasks can use the variable X while the variable X's semaphore indicates that the variable X is being used. Once the waiting task has finished using the variable X, it writes a new value to the variable X semaphore location in order to change the variable X semaphore to indicate that the variable X is once again available.
There is a significant problem that arises in systems that use semaphores to allocate shared system resources. The problem arises when more than one task is polling the semaphore of a shared resource to see if the resource has become available yet. For example, assume task #1 and task #2 are both polling the variable X semaphore. Task #1 is the first to read the variable X semaphore after it has been changed to indicate that the variable X is available. Task #2 now reads the variable X semaphore and also learns that the variable X is available. Neither task #1 nor task #2 is aware that another task is competing for the use of the variable X.
If task #1 receives an interrupt, task #1 must execute a software interrupt routine before resuming where it left off. Meanwhile, task #2 writes a value to the variable X semaphore to indicate that the variable X is now busy. Task #2 then proceeds to use the variable X. Task #1 finishes its interrupt routine and resumes where it left off in its software program. Task #1 left off knowing that the variable X was available. Task #1 thus writes a value to the variable X semaphore to indicate that the variable X is now busy and then proceeds to try to use the variable X. But the variable X is already being used by Task #2. Thus a collision results. As a consequence, the variable X may be corrupted and tasks may receive the incorrect value of variable X. Thus, an approach is needed which allows multiple tasks to effectively and efficiently share common resources.